# 二叉树的直径： https://leetcode-cn.com/problems/diameter-of-binary-tree/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

"""
    这道题我第一下看，还没明白过来。 但是仔细一想， 其实就是求 二叉树任意节点，对应的两颗子树的最大深度之和，的最大值
    那么问题就和 “二叉树的最大深度“ 这题类似了(采用深度优先(后序遍历))， 求每个节点 左右子节点的最大深度之和， 最后返回最大的
"""

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        """
            看清问题后，其实就是求 每个节点的左右子树深度之和， 找到最大值
            利用后序遍历：自底向上求
        """
        maxLength = 0
        def postOrder(node):
            nonlocal maxLength
            if not node: return 0

            left = postOrder(node.left)
            right = postOrder(node.right)
            
            maxLength = max(maxLength, left + right)

            # 左右子树的最大深度 + 1 等于当前树的深度
            return  max(left, right) + 1
        
        postOrder(root)

        return maxLength

